package com.wen;

import com.wen.Part6.DataStructure.AdjacencyMatrix;
import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;
import com.wen.Part6.GraphAlgorithm.impl.TopSort1;
import org.junit.jupiter.api.Test;

import java.io.File;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class Part6_Q {


    Graph getGraph(String path){
        File file = new File(Part6_Q.class.getResource("/" + path).getFile());
        AdjacencyMatrix adjacencyMatrix = new AdjacencyMatrix(file);
        return adjacencyMatrix;
    }

    /**
     * test:
     **/

    // 判断无向图是否是一棵树
    /*
    * 只有n-1条边，且能遍历所有结点
    *
    * */
    @Test
    public void Q_221_1(){

        GraphAlgorithm g = new GraphAlgorithm() {
            void dfs(Graph g, ArrayList<Integer> path, int[] visited, int index, int target){
                if (index == target){
                    System.out.println(path);
                    return;
                }
                for (Integer next : g.getAccessible(index)) {
                    if (visited[next] == 0){
                        visited[next] = 1;
                        path.add(next);
                        dfs(g,path,visited,next,target);
                        path.remove(path.size() - 1);
                        visited[next] = 0;
                    }
                }




            }

            @Override
            public Object solve(Graph g) {
                int start = g.key2Index("v0");
                int[] visited = new int[g.getSize()];
                visited[start] = 1;
                dfs(g,new ArrayList<Integer>(),visited,start,g.key2Index("v3"));
                return null;
            }
        };


        File file = new File(Part6_Q.class.getResource("/question1.txt").getFile());
        AdjacencyMatrix adjacencyMatrix = new AdjacencyMatrix(file);
        adjacencyMatrix.setUnOrder();
        System.out.println(adjacencyMatrix.getSize());
        adjacencyMatrix.solve(g);
    }

    // 判断无向图是否是一棵树
    /*
     * 只有n-1条边，且能遍历所有结点
     * 访问一个点，统计它所有的边
     * 对于无向图，边 = 2 * (n-1)
     * */
    @Test
    public void Q_221_2(){
        Graph graph = getGraph("unorder_map.txt");
        AdjacencyMatrix g = (AdjacencyMatrix) graph;
        g.setUnOrder();


        GraphAlgorithm ga = new GraphAlgorithm() {
            int e; // 统计点
            int v; // 统计边

            void Dfs(Graph g, int[] visited, int index){
                e++;
                for (Integer next : g.getAccessible(index)) {
                    v++;
                    if (visited[next] == 0){
                        visited[next] = 1;
                        Dfs(g,visited,next);
                    }
                }
            }

            @Override
            public Object solve(Graph g) {
                int[] visited = new int[g.getSize()];
                visited[0] = 1;
                Dfs(g,visited,0);
                System.out.println(String.format("点的个数: %d  边的条数 %d", e,v));
                return e == g.getSize() && v == 2 * (g.getSize() - 1);
            }
        };
        System.out.println(g.solve(ga));
    }

    // 非递归 DFS
    /*
     * 多叉树的先序遍历
     * 层序遍历的框架
     * 把队列替换为栈并且从右到左入栈，这样每行第一个元素总是在顶端
     * PS : 多叉树的后序遍历其实就是逆着的先序遍历，最后再逆序
     *  把队列替换为栈并且从左到右入栈，每出栈一个元素，送入另外一个栈
     * */
    @Test
    public void Q_221_3(){
        Graph graph = getGraph("unorder_map.txt");
        AdjacencyMatrix g = (AdjacencyMatrix) graph;
        g.setUnOrder();


        GraphAlgorithm ga = g1 -> {
            int[] visited = new int[g1.getSize()];
            LinkedList<Integer> stack = new LinkedList<>();
            List<String> list = new ArrayList<>();
            stack.push(0);
            visited[0] = 1;
            while (!stack.isEmpty()){
                Integer head = stack.poll();
                list.add(g1.index2Key(head));
                List<Integer> accessible = g1.getAccessible(head);
                for (int next = accessible.size() - 1; next >= 0; next--) {
                    if (visited[accessible.get(next)] == 0){
                        visited[accessible.get(next)] = 1;
                        stack.push(accessible.get(next));
                    }
                }
            }
            System.out.println(list);
            return null;
        };
        g.solve(ga);
    }

    // 输出i 到 j 的所有路径
    /*
     * 多叉树的先序遍历
     * 层序遍历的框架
     * 把队列替换为栈并且从右到左入栈，这样每行第一个元素总是在顶端
     * PS : 多叉树的后序遍历其实就是逆着的先序遍历，最后再逆序
     *  把队列替换为栈并且从左到右入栈，每出栈一个元素，送入另外一个栈
     * */
    @Test
    public void Q_221_5(){

        Graph graph = getGraph("unorder_map.txt");
        AdjacencyMatrix g = (AdjacencyMatrix) graph;
        g.setUnOrder();

        GraphAlgorithm ga = new GraphAlgorithm() {
            void dfs(Graph g,int[] visited,List<String> path, int index, int target){
                if (index == target){
                    System.out.println(path);
                    return;
                }
                for (Integer next : g.getAccessible(index)) {
                    if (visited[next] == 0){
                        visited[next] = 1;
                        path.add(g.index2Key(next));
                        dfs(g,visited,path,next,target);
                        visited[next] = 0;
                        path.remove(path.size()-1);
                    }
                }
            }
            @Override
            public Object solve(Graph g) {
                int[] visited = new int[g.getSize()];
//                LinkedList<Integer> stack = new LinkedList<>();
                List<String> path = new LinkedList<>();
                path.add("a");
                visited[g.key2Index("a")] = 1;
                dfs(g,visited,path,g.key2Index("a"),g.key2Index("h"));
                return null;
            }
        };
        g.solve(ga);
    }

    // DFS实现拓扑排序
    /*
     * 原理
     * 子节点的DFS一定在父节点之后
     * 因此只要在函数结尾节点加入栈中，得到的就是拓扑排序
     * 同理，只要在函数结尾节点加入队列中，得到的就是逆拓扑排序
     * 由于拓扑排序的图可能有多个连通分量，因此需要多连通分量的DFS
     * */
    @Test
    public void Q_237_9(){

        Graph graph = getGraph("topo.txt");
        AdjacencyMatrix g = (AdjacencyMatrix) graph;

        int[] visited = new int[g.getSize()];
        GraphAlgorithm ga = new GraphAlgorithm() {
            void dfs(Graph g, LinkedList<String> stack, int[] visited,int index){
                visited[index] = 1;
                for (Integer next : g.getAccessible(index)) {
                    if (visited[next] == 0){
                        dfs(g,stack, visited, next);
                    }
                }
                stack.addFirst(g.index2Key(index));
            }
            @Override
            public Object solve(Graph g) {

                LinkedList<String> stack = new LinkedList<>();
                for (int i = 0; i < g.getSize(); i++) {
                    if (visited[i] == 0){
                        dfs(g,stack,visited, i);
                    }
                }
                System.out.println(stack);
                return null;
            }
        };
        g.solve(ga);
        g.solve(new TopSort1());
    }


}
